package niuke.week3;

/**
 给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？
 字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符
 （例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）

 例如：
 S="nowcccoder", T = "nowccoder"
 返回3
 */
public class NumberOfSubSeq {
    public static void main(String[] args) {
        System.out.println(numDistinct("a","b"));
    }


    public static int numDistinct (String s, String t) {
        int m = s.length();
        int n = t.length();
        System.out.println(m+" "+n);
        int [][]dp = new int[m+1][n+1];
        //dp_i,j   s1_0,i 的子序列为  s2_0,j 的个数

        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + (s.charAt(i-1)==t.charAt(j-1)?dp[i-1][j-1]:0);
            }
        }
        return dp[m][n];
    }
}